using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.InteropServices;

namespace GeoParser
{
	/// <summary>
	/// Compares 2 strings 'naturally', i.e. order a1, a2, a10, a12.
	/// </summary>
	public struct NaturalComparer : IComparer<string>, IComparer
	{
		#region IComparer<T> Members
		public int Compare(string x, string y)
		{
			return NaturalComparer.CompareStrings(x, y);
		}
		#endregion

		#region IComparer Members
		public int Compare(object x, object y)
		{
			return NaturalComparer.CompareStrings(x as string, y as string);
		}
		#endregion

		public static int CompareStrings(string a, string b)
		{
			if (string.IsNullOrEmpty(a))
			{
				if (string.IsNullOrEmpty(b))
					return 0;
				else
					return -1;
			}
			else
			{
				if (string.IsNullOrEmpty(b))
					return 1;
			}

			return StrCmpLogicalW(a, b);
			//return NativeCompareStrings(a, b);
		}

		/// <summary>
		/// This is the same library Explorer uses to sort filenames.
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <returns></returns>
		[DllImport("Shlwapi.dll", CharSet = CharSet.Unicode)]
		private static extern int StrCmpLogicalW(string a, string b);

		/// <summary>
		/// A native C# implementation of the natural comparer algorithm.
		/// </summary>
		/// <param name="a"></param>
		/// <param name="b"></param>
		/// <returns></returns>
		private static int NativeCompareStrings(string a, string b)
		{
			bool sp1 = Char.IsLetterOrDigit(a, 0);
			bool sp2 = Char.IsLetterOrDigit(b, 0);
			if (sp1 && !sp2)
				return 1;
			if (!sp1 && sp2)
				return -1;

			int i1 = 0;
			int i2 = 0;
			int r = 0;
			while (true)
			{
				bool c1 = Char.IsDigit(a, i1);
				bool c2 = Char.IsDigit(b, i2);
				if (!c1 && !c2)
				{
					bool letter1 = Char.IsLetter(a, i1);
					bool letter2 = Char.IsLetter(b, i2);
					if ((letter1 && letter2) || (!letter1 && !letter2))
					{
						if (letter1 && letter2)
						{
							r = Char.ToLower(a[i1]).CompareTo(Char.ToLower(b[i2]));
						}
						else
						{
							r = a[i1].CompareTo(b[i2]);
						}
						if (r != 0)
							return r;
					}
					else if (!letter1 && letter2)
						return -1;
					else if (letter1 && !letter2)
						return 1;
				}
				else if (c1 && c2)
				{
					r = CompareNum(a, ref i1, b, ref i2);
					if (r != 0)
						return r;
				}
				else if (c1)
				{
					return -1;
				}
				else if (c2)
				{
					return 1;
				}

				i1++;
				i2++;
				if ((i1 >= a.Length) && (i2 >= b.Length))
					return 0;
				else if (i1 >= a.Length)
					return -1;
				else if (i2 >= b.Length)
					return -1;
			}
		}

		private static int CompareNum(string s1, ref int i1, string s2, ref int i2)
		{
			int nzStart1, nzStart2;
			int nzLength1, nzLength2;
			int length1, length2;

			GetNumberMetrics(s1, ref i1, out nzStart1, out nzLength1, out length1);
			GetNumberMetrics(s2, ref i2, out nzStart2, out nzLength2, out length2);
	
			// If the lengths differ, we have a shortcut
			if (nzLength1 < nzLength2)
				return -1;
			else if (nzLength1 > nzLength2)
				return 1;

			// Compare number character by character
			for (int j1 = nzStart1, j2 = nzStart2; j1 <= i1; j1++, j2++)
			{
				int r = s1[j1].CompareTo(s2[j2]);
				if (r != 0)
					return r;
			}

			// Only thing left to compare is the true length of the number
			return length2.CompareTo(length1);
		}

		private static void GetNumberMetrics(string str, ref int index, out int nzStart, out int nzLength, out int length)
		{
			nzStart = index;

			int end = index;
			ScanToNumberEnd(str, index, ref end, ref nzStart);

			int start = index;
			index = end - 1;
			nzLength = end - nzStart;
			length = end - start;
		}

		private static void ScanToNumberEnd(string s, int start, ref int end, ref int nzStart)
		{
			nzStart = start;
			end = start;
			bool countZeros = true;
			while (Char.IsDigit(s, end))
			{
				if (countZeros && s[end].Equals('0'))
					nzStart++;
				else
					countZeros = false;

				end++;
				if (end >= s.Length)
					break;
			}
		}
	}
}